HW#4 --- last modified February 10 2019 21:57:31..

Solution set.

Due date: Dec 7

Files to be submitted:
  Hw4.zip

Purpose: To learn more about circuits, lower bounds proofs, random computation models, and interactive proofs.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO4 -- Know properties of the randomized classes RP, BPP.

LO6 -- Be able to explain interactive proof characterizations of classes like PSPACE.

LO7 -- Explain at least one circuit lower bound technique such as Razborov's techniques for monotone circuits or switching lemma techniques

Specification: This homework consists in doing the following problems:

1. Prove that the language `{langle x, sqrt(x) rangle | \mbox(string ) x \mbox( encodes a natural number in binary)}` is in `NC`.
2. Show `BPP` is closed under unions, intersection, and complements of its members.
3. Do Exercise 7.4 out of the book concerning error reduction in `RP`.
4. Do Exercise 8.1 about `IP` in the book.
5. Do Exercise 14.6 out of the book concerning Razborov Smolensky lower bounds.

On the day your homework is due I will ask each group to present one problem to me in class.

If you scored above 8 on Hw2 and you work for Hw3 with someone who scored below 8 on Hw2, I will give you a 1pt bonus. Similarly, if you scored below 8 on Hw2 and you work for Hw3 with someone who scored above 8 on Hw2, I will give you a 1pt bonus. Be advised though that all group members must be prepared to answer any question on class presentation day.

Point Breakdown